МІНІСТЕРСТВО ОСВІТИ І НАУКИ МОЛОДІ ТА СПОРТУ УКРАІНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
КАФЕДРА АСУ
ЗВІТ
до лабораторної роботи № 1
з дисципліни:
«Методи і засоби комп’ютерних інформаційних технологій»
на тему
«ВИЗНАЧЕННЯ ЕНТРОПІЙНИХ ХАРАКТЕРИСТИК ОБ’ЄКТІВ КОМП’ЮТЕРНИХ МЕРЕЖ»
Мета роботи: навчитися визначати ентропії джерела інформації, приймача, каналу зв’язку, системи взаємозв’язаних об’єктів.
Теоретичні відомості
Ентропія джерела інформації Х, що генерує незалежні повідомлення xi, обчислюється за формулою:
, (1)
де p(xi)- ймовірність появи повідомлення xi; N - кількість можливих повідомлень (символів, станів об’єкту)
Властивості ентропії
Ентропія завжди невід’ємна: .
Ентропія максимальна, коли значення xi випадкової величини X рівноймовірні:
. (2)
Максимальне значення ентропії
. (3)
Для полегшення обчислень ентропії використовують наведену у додатку 1 таблицю значень добутків
Розглянемо систему, що є об’єднанням двох статистично взаємозв’язаних об’єктів, наприклад, джерела Х з можливими станами x1, xi, xn та приймача Y з можливими станами y1, yj, ym...
Сумісна ентропія системи:
, (4)
де ( ймовірність сумісної появи i-го стану в об’єкті X та j-го стану в об’єкті Y.
Якщо об’єкти X та Y незалежні, то сумісна ентропія дорівнює сумі ентропій окремих об’єктів:
. (5)
Ентропія об’єкту Y (приймача), знайдена за умови, що об’єкт Х згенерував повідомлення хi, називається частковою умовною ентропією об’єкту Y. Її визначають за формулою:
(6)
де p(yj/xi) ( ймовірність події yj за умови, що в об’єкті X відбулася подія xi або ймовірність того, що приймач прийме символ yj за умови, що джерело передало символ xi.
Середню або повну умовну ентропію об’єкту Y відносно об’єкту X називають просто умовною ентропією, позначають H(Y/X) і визначають за формулою:
. (7)
Для незалежних об’єктів
, (8)
. (9)
Формули (10) та (11) показують взаємозв’язок ентропії об’єкту, сумісної та умовної ентропій.
(10)
, (11)
де H(X) ( ентропія (безумовна) об’єкту Х;
H(Y) ( ентропія (безумовна) об’єкту Y;
H(X,Y) – сумісна ентропія;
H(Y/X) ( умовна ентропія об’єкту Y відносно об’єкту Х;
H(X/Y) ( умовна ентропія об’єкту X відносно об’єкту Y.
Через часткову і повну умовну ентропії описують інформаційні втрати при передачі даних в каналі зв'язку з завадами. Для цього застосовують так звані канальні матриці. В якості елементів канальної матриці звичайно використовують умовні ймовірності p(yj/xi) отримання приймачем Y символу yj за умови, що джерелом Х був відправлений символ xi. При цьому канальна матриця P(Y/X)має наступний вигляд:
. (12)
Ймовірності, що є елементами головної діагоналі матриці, описують ймовірність правильного прийому. Втрати, які мали місце при передачі сигналу xi, описуються через часткову умовну ентропію:
(13)
Для обчислення всіх втрат при передачі всіх сигналів використовується умовна (повна) ентропія:
(14)
Для визначення ентропії приймача H(Y) за умови, що відома ентропія джерела H(X) і канальна матриця P(Y/X), необхідно знайти ймовірності появи символів на вході приймача p(yj):
. (15)
Взаємозв'язок переданих і отриманих символів може бути описаний також матрицею сумісних ймовірностей P(X,Y):
. (16)
Сума всіх елементів стовпчика з номером j дає p(yj), сума рядка з номером i дорівнює p(xi), а сума всіх елементів ...